1. Field of the Invention
The present invention relates to a data processing method for designing a layout of a large scale integrated (LSI) circuit and a recording medium incorporating therein a program for such data processing. More particularly, the present invention relates to a data processing method for calculating and storing in a memory to deform a data structure of layout designing data in which cells having geometry information and also having reference information to refer to geometry information of other cells are hierarchically combined with each other.
2. Description of the Related Art
Data for designing a physical layout for designing LSI are composed in such a manner that data, which are referred to as cells, are hierarchically combined with each other. Each cell has geometry information and reference information used for referring to geometry information of another cell. In the case where a photo-mask or printed board is manufactured by using such layout designing data, in order to conduct logical operations (different logical operations include such ones as OR, AND, XOR, NOT, SUB, and positive- and negative-resizing) between the figures of the cells, the hierarchical structure is collapsed, that is, the hierarchical structure is deformed to be a flat structure, and the calculation is conducted.
Each cell C is composed of geometry information xe2x80x9cfxe2x80x9d, which is directly owned by the cell concerned, and also composed of reference information (s, a) for referring to another cell. The relation between these pieces of information is expressed by the following expression (1).
xe2x80x83C=f+(s, a)xe2x80x83xe2x80x83(1)
In the above expression, xe2x80x9csxe2x80x9d indicates that the geometry information xe2x80x9cfxe2x80x9d of another cell is simply referred to once, that is, xe2x80x9csxe2x80x9d includes a piece of positional information for directing movement, rotation and reflection of geometry information xe2x80x9cfxe2x80x9d. In the above expression, xe2x80x9caxe2x80x9d indicates that geometry information xe2x80x9cfxe2x80x9d to be referred to should be referred to as two-dimensional array arrangement of n columns and m rows. Note that xe2x80x9csxe2x80x9d and xe2x80x9caxe2x80x9d can be applied not only to xe2x80x9cfxe2x80x9d but also to xe2x80x9csxe2x80x9d or xe2x80x9caxe2x80x9d of another cell.
In short, cascading hierarchical reference can be represented by arbitrary multiplication of xe2x80x9csxe2x80x9d and xe2x80x9caxe2x80x9d. In this case, the reason why xe2x80x9cfxe2x80x9d is expressed by a bold letter is that xe2x80x9cfxe2x80x9d can be generally processed as a vector composed of a plurality of polygons. The reason why xe2x80x9c(s, a)xe2x80x9d are expressed by bold letters is that xe2x80x9c(s, a)xe2x80x9d can be processed as vectors having a position (direction) and intensity (quantity of data).
FIG. 4 is a view schematically showing a model of the composition in which a plurality of cells compose one set of layout designing data, which are correlated with each other, in a hierarchical structure.
FIG. 4 is interpreted as follows. (1) Cell C0 refers to cell C1 by the arrangement of al. Also, cell C0 refers to cell C2 by the arrangement of a2. At this time, cell C0 is not referred by any other cell. Therefore, cell C0 is referred to as xe2x80x9ctop cell Ctxe2x80x9d.
(2) Cell C1 singly refers to cell C3 by S1, S2, S3 and S4, that is, cell C1 singly refers to cell C3 four times in total. Further, cell C1 singly refers to cell C4 by S5.
(3) Cell C2 refers to cell C3 by a3. Cell C2 refers to cell C4 by a6. Cell C2 singly refers to cell C4 by s6 and s7 two times in total.
(4) Cells C3 and C4 are referred to by other cells and do not refer to other cells by themselves. Therefore, cells C3 and C4 are referred to as atom cells Ca.
The above relations are expressed by the following expression (2).
C0=f0+a1C1+a2C2C1=f1+s1C3+s2C3+s3C3+s4C3+s5C4C2=f2+a3C3+a6C4+s6C4+s7C4C3=f3C4=f4xe2x80x83xe2x80x83(2)
Conducting operation (OR processing) by collapsing the hierarchical structure is the same as expressing top cell Ct=C0 only by f, s and a. When expression (2) is actually expanded, the following expression (3) can be obtained, the right side of which is composed of 12 terms. In this connection, the sign + expresses that the developed geometry information must be subjected to OR operation.
C0=f0+a1f1+a2f2+a1s1f3+a1s2f3+a1s3f3+a1s4f3+a1s5f4+a2a3f3+a2a6f4+a2s6f4+a2s7f4xe2x80x83xe2x80x83(3)
In expression (3), when not less than two operators act on f as shown by a2a3f3, the operators act in the order of closeness to f. That is:
a2a3f3=(a2(a3f3))
Therefore, f3 is referred by the arrangement of a3. The result is referred by the arrangement of a2. In this connection, the commutative law of operators is not established. That is:
aiajfxe2x89xa0ajaif(aixe2x89xa0aj)
The actual layout designing data is complicated in many cases. Therefore, it is not unusual that the number of terms on the right side of the expression (3) exceeds one million. An OR operation is conducted after these terms have been classified by a spatial positional relation. Therefore, it is necessary that all these terms are stored in the memory. That is, when the number of the terms on the right side of the expression (3) is large, the memory requirement for computation must be increased. Accordingly, it takes a long operation time and, further the manufacturing cost is increased.
The present invention has been accomplished to solve the above problems of the prior art.
It is an object of the present invention to provide a data processing method and a recorded medium incorporating therein a program capable of reducing the operation processing time by deforming and simplifying the data structure of layout designing data composed of cells which are hierarchically combined with each other.
In order to solve the above problems, the present invention is composed as follows.
The present invention provides a method of data processing for calculating and storing in a memory so as to deform a data structure of layout designing data in which cells having geometry information of the cells concerned and also having reference information to refer to geometry information of another cell are hierarchically combined with each other, the method of data processing being characterized in that: cell Cx of an upper layer for referring to atom cell Ca, cell Ca having only geometry information and not referring to geometry information of a lower layer by itself, is made to have the geometry information of atom cell Ca by copying; reference information of cell Cx is deleted and cell Cx is replaced with Cxe2x80x2x; cell Cy of an upper layer, which refers to geometry information of cell Cxe2x80x2x concerned, is made to have geometry information of cell Cxe2x80x2x by copying; reference information of cell Cy is deleted and cell Cy is replaced with cell Cxe2x80x2y; and the above operation is repeated so that the data structure hierarchically combined from the top cell Ct of the uppermost layer, which is not referred by any other cell, to the atom cell Ca of the lowermost layer, is deformed and stored.
In this case, it is preferable that only when a quantity g of data obtained from geometry information and reference information of cells Cx, Cy, . . . , which refer to the cells of a lower layer including atom cell Ca, is not more than threshold value w which is set for each hierarchy to which each cell Cx . . . Cy, belongs, geometry information of the lower layer cell is made to copy on geometry information of each cell Cx, Cy, and reference information is deleted and each cell Cx, Cy is replaced with Cxe2x80x2x, Cxe2x80x2y, . . .
According to another aspect of the present invention is to provide a recorded medium incorporating therein a program to carry out the above-mentioned method.